package leetcode.slidwidow;

import java.util.Arrays;
import java.util.HashSet;

public class Lc3297 {


    public long validSubstringCount(String word1, String word2) {
        long ans = 0;
        int sum = word2.length();
        int[] cnt = new int[26];
        HashSet<Character> word2Set = new HashSet<>();
        for (char c : word2.toCharArray()) {
            cnt[c - 'a']++;
            word2Set.add(c);
        }
        int n = word1.length();
        for (int i = 0, j = 0; j < word1.length(); j++) {
            char c = word1.charAt(j);
            if (word2Set.contains(c)) {
                if (cnt[c - 'a'] > 0) sum--;
                cnt[c - 'a']--;
                if (sum == 0) {
                    c = word1.charAt(i);
                    while (sum == 0 && (!word2Set.contains(c) || cnt[c - 'a'] <= 0)) {
                        if (word2Set.contains(c)) {
                            cnt[c - 'a']++;
                            if (cnt[c - 'a'] > 0) sum++;
                        }
                        ans += n - j;
                        i++;
                        if (i > j) break;
                        c = word1.charAt(i);
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Lc3297 lc3297 = new Lc3297();
        String s1 = "dccdceee", s2 = "cec";
        System.out.println(lc3297.validSubstringCount(s1, s2));
        long x = 2935147928L;
        System.out.println();
    }


}
